package main

import (
	"fmt"
)

/*
有n杯咖啡会在不同时间点被喝完 drink[]；洗咖啡的机器只有一台，耗时a秒；晾干的话，耗时b秒；
求最快多久能处理完数组中的咖啡杯
*/
// index 为当前处理杯子编号，washDoneTime 为洗杯机用完的时间戳
func getMinTime(drink []int, a int, b int, index int, washDoneTime int) int {
	wash := Max(drink[index], washDoneTime) + a
	dry := drink[index] + b
	if index == len(drink)-1 {
		return Min(wash,dry)
	}
	
	//wash 时间点！
	p1 := getMinTime(drink, a, b, index+1, wash)
	//dry
	p2 := getMinTime(drink, a, b, index+1, washDoneTime)

	s++
	// fmt.Println(index, wash, p1, dry, p2)
	return Min(Max(wash, p1), Max(dry, p2))
}

func dp(drink []int, a int, b int) int {
	len := len(drink)
	limit := drink[len-1] + len * a    ///
	var dp [][]int
	for i := 0; i < len; i++ {
		dp = append(dp, make([]int, limit+1))
	}
	
	for i := 0; i < limit+1; i++ {
		wash := Max(i, drink[len-1]) + a
		dry := drink[len-1] + b
		dp[len-1][i] = Min(wash,dry)
	}

	for idx := len-2; idx >= 0; idx-- {
		limit = drink[idx] + a * (idx + 1)    ///
		// fmt.Println(limit)
		for w := 0; w < limit+1; w++ {
			
			//wash 时间点！
			wash := Max(drink[idx], w) + a
			p1 := dp[idx+1][wash]
			//dry
			dry := drink[idx] + b
			p2 := dp[idx+1][w]
			dp[idx][w] = Min(Max(wash, p1), Max(dry, p2))

		}
	}

	fmt.Println(len * (drink[len-1] + len * a))

	return dp[0][0]
}

var s int 

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func Min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var drink []int = []int{1,1,5,5,7,10,12,12,12,12,12,12,15}
	res := getMinTime(drink, 3, 10, 0, 0)
	fmt.Println(res)
	fmt.Println(s)
	fmt.Println(dp(drink, 3, 10))
}